__metaclass__ = type

import random

infinity = 1.0e400

class Struct:
    """Create an instance with argument=value slots.
    This is for making a lightweight object whose class doesn't matter.
    Ex: s = Struct(a=1, b=2); s.a ==> 1; s.a = 3; s ==> Struct(a=3, b=2)
    """
    def __init__(self, **entries):
        self.__dict__.update(entries)

    def __cmp__(self, other):
        if isinstance(other, Struct):
            return cmp(self.__dict__, other.__dict__)
        else:
            return cmp(self.__dict__, other)

    def __repr__(self):
        args = ['%s=%s' % (k, repr(v)) for (k, v) in vars(self).items()]
        return 'Struct(%s)' % ', '.join(args)

# Functions on sequences of numbers
# A lot of programing is finding the best value that satisfies some condition;
# so there are three versions of argmin/argmax, depending on what you want to
# do with ties: return the first one, return them all, or pick at random.

def argmin(seq, fn):
    """Return an element with lowest fn(seq[i]) score; tie goes to first one.
    Ex: argmin(['one', 'to', 'three'], len) ==>  'to'
    """
    best = seq[0]; best_score = fn(best)
    for x in seq:
        x_score = fn(x)
        if x_score < best_score:
            best, best_score = x, x_score
    return best

def argmin_list(seq, fn):
    """Return a list of elements of seq[i] with the lowest fn(seq[i]) scores.
    Ex: argmin_list(['one', 'to', 'three', 'or'], len) ==>  ['to', 'or']
    """
    best_score, best = fn(seq[0]), []
    for x in seq:
        x_score = fn(x)
        if x_score < best_score:
            best, best_score = [x], x_score
        elif x_score == best_score:
            best.append(x)
    return best

def argmin_random_tie(seq, fn):
    """Return an element with lowest fn(seq[i]) score; break ties at random.
    Thus, for all s,f: argmin_random_tie(s, f) in argmin_list(s, f)
    """
    best_score = fn(seq[0]); n = 0
    for x in seq:
        x_score = fn(x)
        if x_score < best_score:
            best, best_score = x, x_score; n = 1
        elif x_score == best_score:
            n += 1
            if random.randrange(n) == 0:
                best = x
    return best

def argmax(seq, fn):
    """Return an element with highest fn(seq[i]) score; tie goes to first one.
    Ex: argmax(['one', 'to', 'three'], len) ==> 'three'
    """
    return argmin(seq, lambda x: -fn(x))

def argmax_list(seq, fn):
    """Return a list of elements of seq[i] with the highest fn(seq[i]) scores.
    Ex: argmax_list(['one', 'three', 'seven'], len) ==> ['three', 'seven']
    """
    return argmin_list(seq, lambda x: -fn(x))

def argmax_random_tie(seq, fn):
    """Return an element with highest fn(seq[i]) score; break ties at random.
    """
    return argmin_random_tie(seq, lambda x: -fn(x))

def num_or_str(x):
    """The argument is a string; convert to a number if possible, or strip it.
    Ex: num_or_str('42') ==> 42; num_or_str(' 42x ') ==> '42x'
    """
    if isnumber(x): return x
    try:
        return int(x)
    except ValueError:
        try:
            return float(x)
        except ValueError:
            return str(x).strip()

def abstract():
    """Indicate abstract methods that should be implemented in a subclass.
    Ex: def m(): abstract() # Similar to Java's 'abstract void m()'
    """
    raise NotImplementedError(caller() + ' must be implemented in subclass')

def caller(n=1):
    """Return the name of the calling function n levels up in the frame stack.
    Ex: caller(0) ==> 'caller'; def f(): return caller(); f() ==> 'f'
    """
    import inspect
    return  inspect.getouterframes(inspect.currentframe())[n][3]

def parse_move(move):
    """A move is represented by a string like:
    X:5a-6b 6b-7c 7c-8d

    We return back (player, from, to, steps)
    """

    move = move.strip('\n')
    move = move.strip()
    player, moves = move.split(':')
    parts = moves.split(' ')
    parts = filter(None, parts)
    steps = []
    start = None
    for part in parts:
        a, b = part.split('-')
        a = (int(a[0]), a[1])
        b = (int(b[0]), b[1])
        if start is None:
            start = a
            steps.append(b)
            continue
        if a not in steps:
            steps.append(a)
        if b not in steps:
            steps.append(b)
    end = steps[-1]
    if len(steps) == 1:
        steps = ()
    return player, start, end, tuple(steps)
